#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start

struct cmp {
    bool operator()(const pair<int, int> & p1, const pair<int, int> & p2) {
        return p1.second > p2.second;
    }
};

class Solution {
public:
    // 维护一个k大小的堆, 每次的代价为log k
    // 之前的思路没有维护堆的大小固定, 因此会引入额外的复杂度
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q; unordered_map<int, int> counter;
        for (int i = 0; i < nums.size(); i++) {
            counter[nums[i]]++;
        }
        for (auto x: counter) {
            if (q.size() < k) q.push(x);
            else {
                if (x.second > q.top().second) {
                    q.pop(); q.push(x);
                }
            }
        }
        vector<int> res;
        while (!q.empty()) {
            res.push_back(q.top().first);
            q.pop();
        }
        return res;
    }
};
// @lc code=end

